"""
1. 单链表结构描述
    一个node节点包含， value值和next下一节点
    通过next将多个节点连起来形成链表，单链表就是指只有一个方向
2. 优点
    内存空间不需要连续，不需要先申请内存，用的时候添加新结点就行
    

3. 功能实现
    . 创建链表
    . 尾插
    . 头插
    . 查询
    . 删除
    . 链表反转， 1->2->3->4 变为 4->3->2->1
    . 判断长度
"""

# 首先创建一个节点

class Node:
    def __init__(self, value):
        """
            @value: 数据值
            @next_node: 下一个节点 
        """
        self.value = value
        self.next_node = ""
        

# 创建链表
class NodeList:
    def __init__(self, node: Node = None):
        """
            @node: 节点， 链表应该有一个头节点，标识起始位置
        """
        self.head = node
    
    """ 因为再很多情况下都需要判断链表是否为空所以添加单独方法供调用 """
    
    def __is_empty(self):
        if self.head:
            return False
        return True
    
    
    def append_node(self, value):
        node = Node(value)
        # 尾插
        if self.__is_empty():
            # 空的
            self.head = node
            return True
        index_node = self.head
        # 遍历到尾,
        while index_node.next_node: # 下一个节点不是空
            index_node = index_node.next_node
        # 插入
        index_node.next_node = node
        return True
    
    def traverse(self):
        """ 遍历节点 """
        if self.__is_empty():
            """ 空的 """
            print(None)
            return 
        # 遍历链表
        index_node = self.head
        # 如果有当前节点
        while index_node:
            print(index_node.value)
            index_node = index_node.next_node
        # 输出当前节点, 处理的是最后一个节点和只有一个节点的情况
        
    def head_insert(self, value):
        """ 头插 """
        node = Node(value)
        # 空的
        if self.__is_empty():
            self.head = node
            return 
        # 非空
        node.next_node = self.head
        self.head = node
        
    
    def get_length(self):
        """ 判断长度 """
        if self.__is_empty():
            return 0
        
        index_node = self.head
        length = 1
        
        while index_node.next_node:
            length += 1
            index_node = index_node.next_node
        return length
    
    def reverse_node_list(self):
        """ 链表反转, 这个相当于把链表拆分重组了 """
        if self.__is_empty():
            return None
        """ 以下注释是第一次执行 """
        "1 2 3 4"
        # 过程
        """
         因为有next 我也直接把后续写出来了， 方便理解， 但是 通过next 进行链接的并没有开辟新的 链表空间
            第一步
                "index_node = 2 3 4"
                "head = 1 None"
                "pre = 1 None"
                "head = 2 3 4"
            第二步：
                "index_node= 3 4"
                "head = 2 1 None"
                "pre = 2 1 None "
                "head" = "3 4"
            三：
                "index_node= 4"
                "head = 3 2 1 None"
                "pre =3 2 1 None "
                "head" = "4"
            四、
                "index_node= None"
                "head = 4 3 2 1 None"
                "pre =4 3 2 1 None "
                "head" = None"
            五、
                head = pre = "4 3 2 1 None"
        """
        index_node = ""
        pre_node = ""
        while self.head:
            # 可以理解为将读到的数据放到头节点
            # index_node = 2 同时index_node 知道后边的节点
            index_node = self.head.next_node
            # 1 -> None， 将head 放到头
            self.head.next_node = pre_node
            # pre_node = 1
            # pre 总是记录最新的head的位置
            pre_node = self.head
            # 2， head 往后移
            self.head = index_node
            # head 一直在移动
        # 再次将head放到头
        self.head = pre_node
            
    def remove(self, value):
        """ 删除节点 """
        # 删除节点需要两个边量， 一个指向上一个节点， 一个指向下一个节点    
        pre = None
        cur = self.head
        while cur:
            # 找到了
            if cur.value == value:
                # 说明还没移动, 是头节点
                if pre == None:
                    cur = cur.next_node
                    # 换头
                    self.head = cur
                else:
                    pre.next_node = cur.next_node
                    cur = cur.next_node
            else:
                pre = cur
                cur = cur.next_node
                
    def insert(self, pos, value):
        """ 插入 
            @ pos： 是位置
            @ value : 是插入的值
        """
        if pos < 0 or not self.head:
            # 默认头插
            self.head_insert(value)    
            return 
        elif pos >= self.get_length():
            # 默认尾插
            self.append_node(value)
        else:
            cur = self.head
            node = Node(value)
            count = 0
            while cur:
                if count == pos:
                    cur.next_node, node.next_node = node, cur.next_node
                    return
                count += 1
                cur = cur.next_node


if __name__ == "__main__":

    node_list = NodeList()
    # 尾插
    for i in range(1, 5):
        node_list.append_node(i)
    
    # 遍历
    node_list.traverse()
    # # 头插
    node_list.head_insert(-1)
    # # 遍历
    node_list.traverse()
    # # 获取长度
    length = node_list.get_length()
    print("长度", length)
    #  反转
    print("反转", "=======================")
    node_list.reverse_node_list()
    # # 遍历
    node_list.traverse()
    print("头插", "=======================")
    node_list.head_insert(4)
    node_list.head_insert(4)
    node_list.head_insert(4)
    # 删除
    print("删除", "=======================")
    node_list.remove(4)
    # # 遍历
    node_list.traverse()
    
    # 插入
    print("插入", "=======================")
    node_list.insert(2, 10)
    # # 遍历
    node_list.traverse()
    
    